package leetcode.editor.cn;
//累加数 是一个字符串，组成它的数字可以形成累加序列。 
//
// 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。 
//
// 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。 
//
// 说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。 
//
// 
//
// 示例 1： 
//
// 
//输入："112358"
//输出：true 
//解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
// 
//
// 示例 2： 
//
// 
//输入："199100199"
//输出：true 
//解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199 
//
// 
//
// 提示： 
//
// 
// 1 <= num.length <= 35 
// num 仅由数字（0 - 9）组成 
// 
//
// 
//
// 进阶：你计划如何处理由过大的整数输入导致的溢出? 
//
// Related Topics 字符串 回溯 👍 438 👎 0


import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution282 {
    boolean res = false;

    public boolean isAdditiveNumber(String num) {
        int maxLent = num.length() / 2;
        for (int i1 = 1; i1 <= maxLent; i1++) {
            int i = i1;
            if (num.charAt(0) == '0') {
                i = 1;
            }
            for (int j = 1; j <= maxLent; j++) {

                if (num.charAt(i) == '0') {
                    backtrack(num, 0, i, i, 1);
                    break;
                }
                if (i + j >= num.length()) break;
                if (res) {
                    return true;
                }
                backtrack(num, 0, i, i, j);
            }

        }
        return res;
    }

    private void backtrack(String num, int fir, int firLength, int sec, int secLength) {
        if (res || (sec + secLength) > num.length()) return;
        long first = Long.parseLong(num.substring(fir, fir + firLength));
        long second = Long.parseLong(num.substring(sec, sec + secLength));
        long re = first + second;
        String s = String.valueOf(re);
        if ((sec + secLength + s.length() <= num.length()) && s.equals(num.substring(sec + secLength, sec + secLength + s.length()))) {
            if (sec + secLength + s.length() == num.length()) {
                res = true;
                return;
            }
            backtrack(num, sec, secLength, sec + secLength, s.length());
        }

    }


    public static void main(String[] args) {
        Solution282 s = new Solution282();
        System.out.println(s.isAdditiveNumber("1023"));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
